//给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,3,4]
//输出：[2,1,4,3]
// 
//
// 示例 2： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1]
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 100] 内 
// 0 <= Node.val <= 100 
// 
//
// Related Topics 递归 链表 👍 1826 👎 0

import leetcodeauto.common.ListNode;

import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution24 {
    public ListNode swapPairs(ListNode head) {
        return func(head);
    }

    ListNode func(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 第三个开始, 递归
        ListNode first = head;
        ListNode second = head.next;
        ListNode restH = func(second.next);

        // 1,2 互换
        ListNode retH = second;
        second.next = first;
        first.next = restH;
        return retH;
    }
}

class Frame {
    ListNode node;
    boolean done;

    public Frame(ListNode node) {
        this.node = node;
    }
}

/**
 * 说明:
 * 递归改迭代套路, 能保证你一定能够改出来, 且不用关心原题背景;
 * 但, 代码会冗余很多. 如, 本题, 根据题意写的迭代方式, LeetCode 官方代码只有 11 行!!
 */
class Solution24_递归2迭代 {
    public ListNode swapPairs(ListNode _head) {
        Stack<Frame> stack = new Stack<>();
        Frame rootFrame = new Frame(_head);
        stack.push(rootFrame);
        ListNode restH = null;
        while (!stack.isEmpty()) {
            Frame currFrame = stack.pop();
            ListNode currNode = currFrame.node;
            if (currNode == null || currNode.next == null) {
                restH = currNode;
                continue;
            }

            if (currFrame.done) {
                ListNode first = currNode;
                ListNode second = currNode.next;
                // 1,2 互换
                ListNode retH = second;
                second.next = first;
                first.next = restH;
                restH = retH;
                continue;
            }

            // ListNode restH = func(second.next);
            stack.push(currFrame);
            stack.push(new Frame(currNode.next.next));
            currFrame.done = true;
        }

        return restH;
    }

}


//leetcode submit region end(Prohibit modification and deletion)
